
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// 这种写法直接利用了数组的一些方法
var searchRange = function (nums, target) {
  return [nums.indexOf(target), nums.lastIndexOf(target)];
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// 这种写法的效率比较高
var searchRange = function (nums, target) {
  let left = -1;
  let right = -1;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      // 第一次找到目标值，记录左边界
      if (left === -1) {
        left = i;
      }
      // 每次遇到目标值都更新右边界（最后一次更新即为最终右边界）
      right = i;
    }
  }

  return [left, right];
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
/* 
为了在排序数组中高效地找到目标值的第一个和最后一个位置，可以使用两次二分查找，
分别定位起始和结束位置。

方法思路
寻找第一个位置：使用二分查找确定目标值的左边界。当中间元素等于目标值时，
继续向左搜索以找到第一个出现的位置。
寻找最后一个位置：使用二分查找确定目标值的右边界。当中间元素等于目标值时，
继续向右搜索以找到最后一个出现的位置。
处理边界情况：如果在任何一次搜索中未找到目标值，直接返回[-1, -1]。
*/
var searchRange = function (nums, target) {
  const left = findLeft(nums, target);
  if (left === -1) return [-1, -1];

  const right = findRight(nums, target);
  return [left, right];
};

function findLeft(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] >= target) {
      right = mid - 1;
      if (nums[mid] === target) {
        result = mid;
      }
    } else {
      left = mid + 1;
    }
  }

  return result;
}

function findRight(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] <= target) {
      left = mid + 1;
      if (nums[mid] === target) {
        result = mid;
      }
    } else {
      right = mid - 1;
    }
  }

  return result;
}